Interval Heap

Operations

全順序集合の$ n要素の部分多重集合を扱う.

空間計算量$ \Theta(n)

$ \mathtt{new}()

空の集合を作成する.

時間計算量$ \Theta(1)

$ \mathtt{min}()

最小の値を取得する.

時間計算量$ \Theta(1)

$ \mathtt{max}()

最大の値を取得する.

時間計算量$ \Theta(1)

$ \mathtt{insert}(x)

$ xを集合に追加する.

時間計算量$ \Theta(\log n)

$ \mathtt{delete\_min}()

最小の値を削除する.

時間計算量$ \Theta(\log n)

$ \mathtt{delete\_max}()

最大の値を削除する.

時間計算量$ \Theta(\log n)

Summary

double-ended priority queue の一種.

通常の Binary Heap の各ノードに 2 つの値が入り, 成す区間の包含関係を維持する.

https://gyazo.com/1cd06f86fb95a4ee4fe87e5869bc06b9

$ \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}を扱う Interval Heap の例

References

Notes

Binary Heap と同様に, 動的配列によって効率的に表現できる.

その場合, $ \mathtt{insert}, \mathtt{delete\_min}, \mathtt{delete\_max}の時間計算量は$ \rm amortizedとなる.

Implementations